import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
}
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    private void dfs(int[] candidates, int target, int i, int sum, List<Integer> ret,boolean[] used){
        if(sum > target) return;
        if(sum == target){
            ans.add(new ArrayList<>(ret));
            return;
        }
        for(int j=i;j<candidates.length; j++){
            if(j > 0 && candidates[j-1] == candidates[j] && !used[j-1]){
                continue;
            }
            if(sum+candidates[j] <= target){
                ret.add(candidates[j]);
                used[j] = true;
                dfs(candidates,target,j+1,sum+candidates[j],ret,used);
                used[j] = false;
                ret.remove(ret.size()-1);
            }
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> ret = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        dfs(candidates,target,0,0,ret,used);
        return ans;
    }

    public static void main(String[] args) {
        StringBuilder stringBuilder = new StringBuilder();
        char[] ch = {'a','b'};
        stringBuilder.append(ch[0]);
        stringBuilder.capacity();
    }
}
class Solution3 {
    List<List<String>> ans = new ArrayList<>();
    private void dfs(String s, int index, List<String> ret){
        if(index == s.length()){
            ans.add(new ArrayList<>(ret));
            return;
        }
        for(int i=index; i<s.length(); i++){
            if(is_reserve(s.substring(index,i+1))){
                ret.add(s.substring(index,i+1));
                dfs(s,index+1,ret);
                ret.remove(ret.size()-1);
            }
        }
    }
    private boolean is_reserve(String s){
        int left = 0;
        int right = s.length()-1;
        while(left<=right&& s.charAt(left)==s.charAt(right)){
            left++;
            right--;
        }
        return left>right?true:false;
    }
    public List<List<String>> partition(String s) {
        List<String> ret = new ArrayList<>();
        dfs(s,0,ret);
        return ans;
    }
}
